package com.java.simple.sort;

import java.util.Arrays;

/**
 * @author zhoujunlin
 * @date 2022年08月09日 10:34
 * @desc 冒泡排序
 * 时间复杂度：n^2
 * (n-1)(n-2)(n-3).....3*2*1=n(n-1)/2=1/2n^2-n/2=O(n^2)
 * https://blog.csdn.net/hcz666/article/details/117810787
 */
public class BubbleSort {

    public static void main(String[] args) {
        int[] numArr = new int[]{1, 10, 2, 8, 3, 4, 7, 6, 5, 9};
        bubbleSortV3(numArr);
        System.out.println(Arrays.toString(numArr));
    }


    private static void bubbleSortV1(int[] numArr) {
        if (numArr == null || numArr.length < 2) {
            return;
        }
        // 外层循环控制交换趟数  n个数据需要循环n-1次
        for (int i = 0; i < numArr.length - 1; i++) {
            for (int j = 0; j < numArr.length - i - 1; j++) {
                if (numArr[j] > numArr[j + 1]) {
                    SwapUtil.swap(numArr, j, j + 1);
                }
            }
        }
    }


    private static void bubbleSortV2(int[] numArr) {
        if (numArr == null || numArr.length < 2) {
            return;
        }
        // 外层循环控制交换趟数  n个数据需要循环n-1次
        for (int i = 0; i < numArr.length - 1; i++) {
            // 是否有序标记  一旦某躺循环里一次交换都没有发生 则说明已经有序  跳出循环
            boolean isSorted = true;
            for (int j = 0; j < numArr.length - i - 1; j++) {
                if (numArr[j] > numArr[j + 1]) {
                    isSorted = false;
                    SwapUtil.swap(numArr, j, j + 1);
                }
            }
            if (isSorted) {
                break;
            }
        }
    }


    private static void bubbleSortV3(int[] numArr) {
        if (numArr == null || numArr.length < 2) {
            return;
        }
        //上次交换位置的索引
        int lastExchangeIdx = 0;
        // 无序排序边界  每次比较到这里就可以了
        int sortBorder = numArr.length - 1;
        // 外层循环控制交换趟数  n个数据需要循环n-1次
        for (int i = 0; i < numArr.length - 1; i++) {
            // 是否有序标记  一旦某躺循环里一次交换都没有发生 则说明已经有序  跳出循环
            boolean isSorted = true;
            for (int j = 0; j < sortBorder; j++) {
                if (numArr[j] > numArr[j + 1]) {
                    isSorted = false;
                    SwapUtil.swap(numArr, j, j + 1);
                    lastExchangeIdx = j;
                }
            }
            sortBorder = lastExchangeIdx;
            if (isSorted) {
                break;
            }
        }
    }

}
